package com.hanxiaozhang.no10leetcode.array;

import java.util.Arrays;

/**
 * 〈一句话功能简述〉<br>
 * 〈〉
 * 给以 m*n 的矩阵，如果某个元素是0的话，就把元素所在的列和行都置0，使用原地算法解决。
 * 简单粗暴的算法使用O(mn)的额外空间，这个方法不太好。稍加改进后使用O(m + n)也不太好 。
 * 请你设计一个使用常量空间的解决方案。
 * <p>
 * 示例 1:
 * 输入:
 * [
 * [1,1,1],
 * [1,0,1],
 * [1,1,1]
 * ]
 * 输出:
 * [
 * [1,0,1],
 * [0,0,0],
 * [1,0,1]
 * ]
 * 示例 2:
 * 输入:
 * [
 * [0,1,2,0],
 * [3,4,5,2],
 * [1,3,1,5]
 * ]
 * 输出:
 * [
 * [0,0,0,0],
 * [0,4,5,0],
 * [0,3,1,0]
 * ]
 * <p>
 * 拓展知识点：
 * 原地算法：一种使用小的，固定数量的额外之空间来转换资料的算法。当算法执行时，输入的资料通常会被要输出的部分覆盖掉。
 * 不是原地算法有时候称为非原地（not-in-place）或不得其所（out-of-place）。
 * 思路：
 * 1.使用深度优先遍历，顺序：从前往后，从上往下。 前面碰到0先不要操作，继续往下走，一直走到最后，然后慢慢的一层一层的处理。
 * 2.深度优先遍历的实现使用递归。
 *
 * @author hanxinghua
 * @create 2024/1/22
 * @since 1.0.0
 */
public class No73SetMatrixZeros {


    public static void main(String[] args) {

        int[][] arr1 = {
                {1, 1, 1},
                {1, 0, 1},
                {1, 1, 1}};

        int[][] arr2 = {
                {0, 1, 2, 0},
                {3, 4, 5, 2},
                {1, 3, 1, 5}};

        setZeroes(arr1);
        System.out.println(Arrays.deepToString(arr1));

        setZeroes(arr2);
        System.out.println(Arrays.deepToString(arr2));

    }

    public static void setZeroes(int[][] matrix) {
        setZeroes(matrix, 0, 0);
    }

    private static void setZeroes(int[][] matrix, int row, int column) {
        // 遍历行
        for (int i = row; i < matrix.length; i++) {
            // 遍历列
            for (int j = column; j < matrix[0].length; j++) {
                if (matrix[i][j] == 0) {

                    // 深度递归遍历
                    setZeroes(matrix, i, j + 1);

                    // 填满行为0
                    Arrays.fill(matrix[i], 0);

                    // 填满列为0
                    for (int index = 0; index < matrix.length; index++) {
                        matrix[index][j] = 0;
                    }
                    return;
                }
            }
            // 遍历下一行时，列归0，从0开始
            column = 0;
        }
    }

}
